<!DOCTYPE html>
<html>
  <head>
    <meta charset='utf-8'>

    <link rel="stylesheet" type="text/css" 
      href="/assets/css/straybirds.css" media="screen" />
    <link rel="stylesheet" type="text/css" 
      href="/assets/css/pygments.css" media="screen" />

    <!-- MathJax Section Start -->

    <script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
    </script>
    <script>
        MathJax.Hub.Config({
              tex2jax: {
              skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
              }
        });
        MathJax.Hub.Queue(function() {
            var all = MathJax.Hub.getAllJax(), i;
            for(i=0; i < all.length; i += 1) {
                all[i].SourceElement().parentNode.className += ' has-jax';
            }
        });
    </script>

    <!-- MathJax Section End -->

    <!-- Google Analytics Start-->
    <script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-48100787-1', 'minixalpha.github.io');
  ga('send', 'pageview');

</script>

    <!-- Google Analytics End -->

    <title>OpenJDK 源码阅读之 TreeMap</title>
  </head>

  <body>
    <div class="container">
      <header>
        <div class="container">
          <h1>
              <a href="/" title="Home Page"> 潇湘夜雨 </a>
          <span class="github-src">
            <a href ="https://github.com/minixalpha/minixalpha.github.io"
               target="_blank"
               title="Fork me on GitHub">
              <img src="/assets/images/GitHub-Mark-Light-32px.png" alt="">
            </a>
          </span>
          </h1>
        </div>
      </header>

      <aside id="left-side">
        <h2> 分类 </h2>
  <ul class="category-list">
      
            
                <li>
                <a href="/categories/源代码阅读"> 源代码阅读 (20) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/设计模式"> 设计模式 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/科研"> 科研 (6) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/思想"> 思想 (2) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/技术"> 技术 (18) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/工具"> 工具 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/虚拟机"> 虚拟机 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/java"> java (11) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/c语言"> c语言 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/读书"> 读书 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/操作系统"> 操作系统 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/英语"> 英语 (10) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/计算机系统"> 计算机系统 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/生活"> 生活 (1) </a>
                </li>
            
      
  </ul>

      </aside>

      <aside id="right-side">
        <h2> 归档 </h2>
  <ul class="archive-list">
    
    
    
        
        
        
        
            
            <li>
                <a href="/2014/08">
                    2014-08 (1)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/07">
                    2014-07 (5)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/05">
                    2014-05 (12)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/04">
                    2014-04 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/03">
                    2014-03 (11)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/02">
                    2014-02 (6)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/01">
                    2014-01 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/11">
                    2013-11 (10)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/10">
                    2013-10 (3)
                </a>
            </li>

        
        
    
        
        
        
        
            
            <li>
                <a href="/2010/09">
                    2010-09 (1)
                </a>
            </li>

        
        
    
  </ul>

      </aside>

      <article>

<h1>OpenJDK 源代码阅读之 TreeMap</h1>

<hr>

<h2>概要</h2>

<ul>
<li>类继承关系</li>
</ul>
<div class="highlight"><pre><code class="text language-text" data-lang="text">java.lang.Object
    java.util.AbstractMap&lt;K,V&gt;
        java.util.HashMap&lt;K,V&gt;
</code></pre></div>
<ul>
<li>定义 </li>
</ul>
<div class="highlight"><pre><code class="text language-text" data-lang="text">public class TreeMap&lt;K,V&gt;
    extends AbstractMap&lt;K,V&gt;
    implements NavigableMap&lt;K,V&gt;, Cloneable, java.io.Serializable
</code></pre></div>
<ul>
<li>要点</li>
</ul>

<p>1) 基于 NavigableMap 实现的红黑树
2) 按 <code>natrual ordering</code> 或者 <code>Comparator</code> 定义的次序排序。
3) 基本操作 <code>containsKey</code>,<code>get</code>,<code>put</code> 有 <code>log(n)</code> 的时间复杂度。
4) 非线程安全</p>

<h2>实现</h2>

<ul>
<li>Comparator</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">private</span> <span class="kd">final</span> <span class="n">Comparator</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;</span> <span class="n">comparator</span><span class="o">;</span>
</code></pre></div>
<p>这说明提供的 <code>Comparator</code> 参数类型是 <code>K</code> 的基类就行。这似乎意味着基类的 <code>Comparator</code> 与导出类的要一致。</p>

<ul>
<li>Entry</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">private</span> <span class="kd">transient</span> <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">root</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
</code></pre></div>
<p><code>root</code> 是这棵红黑树的根，那么从 <code>Entry</code> 的定义可以体现树的结构：</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">static</span> <span class="kd">final</span> <span class="kd">class</span> <span class="nc">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="kd">implements</span> <span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="o">{</span>
    <span class="n">K</span> <span class="n">key</span><span class="o">;</span>
    <span class="n">V</span> <span class="n">value</span><span class="o">;</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">left</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">right</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">parent</span><span class="o">;</span>
    <span class="kt">boolean</span> <span class="n">color</span> <span class="o">=</span> <span class="n">BLACK</span><span class="o">;</span>

    <span class="o">...</span>
<span class="o">}</span>
</code></pre></div>
<p>注意这是个 <code>static final</code> 类，<code>left</code>,<code>right</code>,<code>parent</code> 分别指向左子树，右子树，父结点, <code>color</code> 颜色默认为黑。</p>

<ul>
<li>containsKey</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">containsKey</span><span class="o">(</span><span class="n">Object</span> <span class="n">key</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">return</span> <span class="nf">getEntry</span><span class="o">(</span><span class="n">key</span><span class="o">)</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div><div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">final</span> <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">getEntry</span><span class="o">(</span><span class="n">Object</span> <span class="n">key</span><span class="o">)</span> <span class="o">{</span>
    <span class="c1">// Offload comparator-based version for sake of performance</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">comparator</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">return</span> <span class="nf">getEntryUsingComparator</span><span class="o">(</span><span class="n">key</span><span class="o">);</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">key</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">throw</span> <span class="k">new</span> <span class="nf">NullPointerException</span><span class="o">();</span>
    <span class="n">Comparable</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;</span> <span class="n">k</span> <span class="o">=</span> <span class="o">(</span><span class="n">Comparable</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;)</span> <span class="n">key</span><span class="o">;</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">root</span><span class="o">;</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">p</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">cmp</span> <span class="o">=</span> <span class="n">k</span><span class="o">.</span><span class="na">compareTo</span><span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">key</span><span class="o">);</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="o">)</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
        <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span><span class="o">;</span>
        <span class="k">else</span>
            <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
    <span class="o">}</span>
    <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>关键操作 <code>containsKey</code> 是通过调用 <code>getEntry</code> 完成其功能的。可以看出，这是通过在红黑树上进行查找完成的，每次比较都会下降到树的下一层，由于红黑树的平衡性，时间复杂度为 <code>log(n)</code>。</p>

<ul>
<li>containsValue</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">containsValue</span><span class="o">(</span><span class="n">Object</span> <span class="n">value</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">for</span> <span class="o">(</span><span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">e</span> <span class="o">=</span> <span class="n">getFirstEntry</span><span class="o">();</span> <span class="n">e</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">;</span> <span class="n">e</span> <span class="o">=</span> <span class="n">successor</span><span class="o">(</span><span class="n">e</span><span class="o">))</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">valEquals</span><span class="o">(</span><span class="n">value</span><span class="o">,</span> <span class="n">e</span><span class="o">.</span><span class="na">value</span><span class="o">))</span>
            <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
    <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>可以看出，对 <code>value</code> 的查找，与对 <code>key</code> 是不同的。是通过 <code>getFirstEntry</code> 取得第一个结点，再通过 <code>successor</code> 遍历实现。</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">final</span> <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">getFirstEntry</span><span class="o">()</span> <span class="o">{</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">root</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">p</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">while</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
    <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>可以看出，这是找到了树中最左边的结点，如果左子树中的值小于右子树，这就意味是第一个比较的结点是最小的结点。</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">static</span> <span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">TreeMap</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">successor</span><span class="o">(</span><span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">t</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">t</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
    <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">t</span><span class="o">.</span><span class="na">right</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">right</span><span class="o">;</span>
        <span class="k">while</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
        <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
        <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">parent</span><span class="o">;</span>
        <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">ch</span> <span class="o">=</span> <span class="n">t</span><span class="o">;</span>
        <span class="k">while</span> <span class="o">(</span><span class="n">p</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">&amp;&amp;</span> <span class="n">ch</span> <span class="o">==</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">ch</span> <span class="o">=</span> <span class="n">p</span><span class="o">;</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">;</span>
        <span class="o">}</span>
        <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
    <span class="o">}</span>
<span class="o">}</span>
</code></pre></div>
<p><code>successor</code> 其实就是一个结点的 <code>下一个结点</code>，所谓 <code>下一个</code>，是按次序排序后的下一个结点。从代码中可以看出，如果右子树不为空，就返回右子树中最小结点。如果右子树为空，就要向上回溯了。在这种情况下，<code>t</code> 是以其为根的树的最后一个结点。如果它是其父结点的左孩子，那么父结点就是它的下一个结点，否则，<code>t</code> 就是以其父结点为根的树的最后一个结点，需要再次向上回溯。一直到 <code>ch</code> 是 <code>p</code> 的左孩子为止。</p>

<ul>
<li>getCeilingEntry</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Gets the entry corresponding to the specified key; if no such entry</span>
<span class="cm"> * exists, returns the entry for the least key greater than the specified</span>
<span class="cm"> * key; if no such entry exists (i.e., the greatest key in the Tree is less</span>
<span class="cm"> * than the specified key), returns {@code null}.</span>
<span class="cm"> */</span>
<span class="kd">final</span> <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">getCeilingEntry</span><span class="o">(</span><span class="n">K</span> <span class="n">key</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">root</span><span class="o">;</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">p</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">cmp</span> <span class="o">=</span> <span class="n">compare</span><span class="o">(</span><span class="n">key</span><span class="o">,</span> <span class="n">p</span><span class="o">.</span><span class="na">key</span><span class="o">);</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span>
                <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
            <span class="k">else</span>
                <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">right</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span><span class="o">;</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">;</span>
                <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">ch</span> <span class="o">=</span> <span class="n">p</span><span class="o">;</span>
                <span class="k">while</span> <span class="o">(</span><span class="n">parent</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">&amp;&amp;</span> <span class="n">ch</span> <span class="o">==</span> <span class="n">parent</span><span class="o">.</span><span class="na">right</span><span class="o">)</span> <span class="o">{</span>
                    <span class="n">ch</span> <span class="o">=</span> <span class="n">parent</span><span class="o">;</span>
                    <span class="n">parent</span> <span class="o">=</span> <span class="n">parent</span><span class="o">.</span><span class="na">parent</span><span class="o">;</span>
                <span class="o">}</span>
                <span class="k">return</span> <span class="n">parent</span><span class="o">;</span>
            <span class="o">}</span>
        <span class="o">}</span> <span class="k">else</span>
            <span class="k">return</span> <span class="n">p</span><span class="o">;</span>
    <span class="o">}</span>
    <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>这个函数看起来有点奇怪，可以从 <code>return</code> 语句，猜想一下这是在做什么，我觉得是在找一个 <code>x.key &gt;= key</code> 的元素，并且 <code>x</code> 是满足条件的元素中最小的。从 <code>23</code> 行看，找到的 <code>p</code>，<code>key</code> 值与参数 <code>key</code> 相等，从 <code>8</code> 行看，又有 <code>key &lt;= p.key</code>，并且 <code>p.left == null</code>。</p>

<p><code>put</code></p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Associates the specified value with the specified key in this map.</span>
<span class="cm"> * If the map previously contained a mapping for the key, the old</span>
<span class="cm"> * value is replaced.</span>
<span class="cm"> *</span>
<span class="cm"> * @param key key with which the specified value is to be associated</span>
<span class="cm"> * @param value value to be associated with the specified key</span>
<span class="cm"> *</span>
<span class="cm"> * @return the previous value associated with {@code key}, or</span>
<span class="cm"> *         {@code null} if there was no mapping for {@code key}.</span>
<span class="cm"> *         (A {@code null} return can also indicate that the map</span>
<span class="cm"> *         previously associated {@code null} with {@code key}.)</span>
<span class="cm"> * @throws ClassCastException if the specified key cannot be compared</span>
<span class="cm"> *         with the keys currently in the map</span>
<span class="cm"> * @throws NullPointerException if the specified key is null</span>
<span class="cm"> *         and this map uses natural ordering, or its comparator</span>
<span class="cm"> *         does not permit null keys</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="n">V</span> <span class="nf">put</span><span class="o">(</span><span class="n">K</span> <span class="n">key</span><span class="o">,</span> <span class="n">V</span> <span class="n">value</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">t</span> <span class="o">=</span> <span class="n">root</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">t</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">compare</span><span class="o">(</span><span class="n">key</span><span class="o">,</span> <span class="n">key</span><span class="o">);</span> <span class="c1">// type (and possibly null) check</span>

        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Entry</span><span class="o">&lt;&gt;(</span><span class="n">key</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="kc">null</span><span class="o">);</span>
        <span class="n">size</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="n">modCount</span><span class="o">++;</span>
        <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
    <span class="o">}</span>
    <span class="kt">int</span> <span class="n">cmp</span><span class="o">;</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">parent</span><span class="o">;</span>
    <span class="c1">// split comparator and comparable paths</span>
    <span class="n">Comparator</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;</span> <span class="n">cpr</span> <span class="o">=</span> <span class="n">comparator</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">cpr</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">do</span> <span class="o">{</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="n">t</span><span class="o">;</span>
            <span class="n">cmp</span> <span class="o">=</span> <span class="n">cpr</span><span class="o">.</span><span class="na">compare</span><span class="o">(</span><span class="n">key</span><span class="o">,</span> <span class="n">t</span><span class="o">.</span><span class="na">key</span><span class="o">);</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="o">)</span>
                <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
            <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span>
                <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">right</span><span class="o">;</span>
            <span class="k">else</span>
                <span class="k">return</span> <span class="n">t</span><span class="o">.</span><span class="na">setValue</span><span class="o">(</span><span class="n">value</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">while</span> <span class="o">(</span><span class="n">t</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="k">else</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">key</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="k">throw</span> <span class="k">new</span> <span class="nf">NullPointerException</span><span class="o">();</span>
        <span class="n">Comparable</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;</span> <span class="n">k</span> <span class="o">=</span> <span class="o">(</span><span class="n">Comparable</span><span class="o">&lt;?</span> <span class="kd">super</span> <span class="n">K</span><span class="o">&gt;)</span> <span class="n">key</span><span class="o">;</span>
        <span class="k">do</span> <span class="o">{</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="n">t</span><span class="o">;</span>
            <span class="n">cmp</span> <span class="o">=</span> <span class="n">k</span><span class="o">.</span><span class="na">compareTo</span><span class="o">(</span><span class="n">t</span><span class="o">.</span><span class="na">key</span><span class="o">);</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="o">)</span>
                <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">left</span><span class="o">;</span>
            <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span>
                <span class="n">t</span> <span class="o">=</span> <span class="n">t</span><span class="o">.</span><span class="na">right</span><span class="o">;</span>
            <span class="k">else</span>
                <span class="k">return</span> <span class="n">t</span><span class="o">.</span><span class="na">setValue</span><span class="o">(</span><span class="n">value</span><span class="o">);</span>
        <span class="o">}</span> <span class="k">while</span> <span class="o">(</span><span class="n">t</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">e</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Entry</span><span class="o">&lt;&gt;(</span><span class="n">key</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="n">parent</span><span class="o">);</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">cmp</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="o">)</span>
        <span class="n">parent</span><span class="o">.</span><span class="na">left</span> <span class="o">=</span> <span class="n">e</span><span class="o">;</span>
    <span class="k">else</span>
        <span class="n">parent</span><span class="o">.</span><span class="na">right</span> <span class="o">=</span> <span class="n">e</span><span class="o">;</span>
    <span class="n">fixAfterInsertion</span><span class="o">(</span><span class="n">e</span><span class="o">);</span>
    <span class="n">size</span><span class="o">++;</span>
    <span class="n">modCount</span><span class="o">++;</span>
    <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p><code>put</code> 的过程，其实是将 <code>(key, value)</code> 加入到红黑树中的过程。如果树是空的，那么创建根结点。否则就要在树中插入结点。这个过程根据 <code>comparator</code> 是否存在设置成了两种方式，其实没什么区别，就是比较方式的不同，都是在树中查找一个合适的位置，如果 <code>key</code> 在树中，就 <code>setValue</code> 设置新值，否则，就在 <code>60-64</code> 行插入新结点。这里有个重要的地方是 <code>65</code> 行的 <code>fixAfterInsertion</code> ，这个很重要，因为这是一棵红黑树，红黑树关键的思想是要保持它的平衡性，插入结点后，平衡性可能被破坏。所以需要 <code>fix</code>。</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/** From CLR */</span>
<span class="kd">private</span> <span class="kt">void</span> <span class="nf">fixAfterInsertion</span><span class="o">(</span><span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">x</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">x</span><span class="o">.</span><span class="na">color</span> <span class="o">=</span> <span class="n">RED</span><span class="o">;</span>

    <span class="k">while</span> <span class="o">(</span><span class="n">x</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">&amp;&amp;</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">root</span> <span class="o">&amp;&amp;</span> <span class="n">x</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">color</span> <span class="o">==</span> <span class="n">RED</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)</span> <span class="o">==</span> <span class="n">leftOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">))))</span> <span class="o">{</span>
            <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">y</span> <span class="o">=</span> <span class="n">rightOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)));</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">colorOf</span><span class="o">(</span><span class="n">y</span><span class="o">)</span> <span class="o">==</span> <span class="n">RED</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">),</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">y</span><span class="o">,</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)),</span> <span class="n">RED</span><span class="o">);</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">));</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="k">if</span> <span class="o">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">rightOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)))</span> <span class="o">{</span>
                    <span class="n">x</span> <span class="o">=</span> <span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">);</span>
                    <span class="n">rotateLeft</span><span class="o">(</span><span class="n">x</span><span class="o">);</span>
                <span class="o">}</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">),</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)),</span> <span class="n">RED</span><span class="o">);</span>
                <span class="n">rotateRight</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)));</span>
            <span class="o">}</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">y</span> <span class="o">=</span> <span class="n">leftOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)));</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">colorOf</span><span class="o">(</span><span class="n">y</span><span class="o">)</span> <span class="o">==</span> <span class="n">RED</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">),</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">y</span><span class="o">,</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)),</span> <span class="n">RED</span><span class="o">);</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">));</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="k">if</span> <span class="o">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">leftOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)))</span> <span class="o">{</span>
                    <span class="n">x</span> <span class="o">=</span> <span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">);</span>
                    <span class="n">rotateRight</span><span class="o">(</span><span class="n">x</span><span class="o">);</span>
                <span class="o">}</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">),</span> <span class="n">BLACK</span><span class="o">);</span>
                <span class="n">setColor</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)),</span> <span class="n">RED</span><span class="o">);</span>
                <span class="n">rotateLeft</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">parentOf</span><span class="o">(</span><span class="n">x</span><span class="o">)));</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
    <span class="n">root</span><span class="o">.</span><span class="na">color</span> <span class="o">=</span> <span class="n">BLACK</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>这是 <code>fixAfterInsertion</code> 的源代码，我不具体解释了，这是一个根据不同情况进行旋转，调整结点颜色的过程，可以参考《算法导论》中的解释。</p>

<ul>
<li>remove</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">public</span> <span class="n">V</span> <span class="nf">remove</span><span class="o">(</span><span class="n">Object</span> <span class="n">key</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">getEntry</span><span class="o">(</span><span class="n">key</span><span class="o">);</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">p</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>

    <span class="n">V</span> <span class="n">oldValue</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">value</span><span class="o">;</span>
    <span class="n">deleteEntry</span><span class="o">(</span><span class="n">p</span><span class="o">);</span>
    <span class="k">return</span> <span class="n">oldValue</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>删除的过程主要调用 <code>delteEntry</code> 完成：</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">private</span> <span class="kt">void</span> <span class="nf">deleteEntry</span><span class="o">(</span><span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">p</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">modCount</span><span class="o">++;</span>
    <span class="n">size</span><span class="o">--;</span>

    <span class="c1">// If strictly internal, copy successor&#39;s element to p and then make p</span>
    <span class="c1">// point to successor.</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">&amp;&amp;</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">s</span> <span class="o">=</span> <span class="n">successor</span><span class="o">(</span><span class="n">p</span><span class="o">);</span>
        <span class="n">p</span><span class="o">.</span><span class="na">key</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">key</span><span class="o">;</span>
        <span class="n">p</span><span class="o">.</span><span class="na">value</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">value</span><span class="o">;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">s</span><span class="o">;</span>
    <span class="o">}</span> <span class="c1">// p has 2 children</span>

    <span class="c1">// Start fixup at replacement node, if it exists.</span>
    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">replacement</span> <span class="o">=</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">?</span> <span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">:</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span><span class="o">);</span>

    <span class="k">if</span> <span class="o">(</span><span class="n">replacement</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="c1">// Link replacement to parent</span>
        <span class="n">replacement</span><span class="o">.</span><span class="na">parent</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">parent</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="n">root</span> <span class="o">=</span> <span class="n">replacement</span><span class="o">;</span>
        <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">p</span> <span class="o">==</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">left</span><span class="o">)</span>
            <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">left</span>  <span class="o">=</span> <span class="n">replacement</span><span class="o">;</span>
        <span class="k">else</span>
            <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">right</span> <span class="o">=</span> <span class="n">replacement</span><span class="o">;</span>

        <span class="c1">// Null out links so they are OK to use by fixAfterDeletion.</span>
        <span class="n">p</span><span class="o">.</span><span class="na">left</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">right</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>

        <span class="c1">// Fix replacement</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">color</span> <span class="o">==</span> <span class="n">BLACK</span><span class="o">)</span>
            <span class="n">fixAfterDeletion</span><span class="o">(</span><span class="n">replacement</span><span class="o">);</span>
    <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">parent</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span> <span class="c1">// return if we are the only node.</span>
        <span class="n">root</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span> <span class="c1">//  No children. Use self as phantom replacement and unlink.</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">color</span> <span class="o">==</span> <span class="n">BLACK</span><span class="o">)</span>
            <span class="n">fixAfterDeletion</span><span class="o">(</span><span class="n">p</span><span class="o">);</span>

        <span class="k">if</span> <span class="o">(</span><span class="n">p</span><span class="o">.</span><span class="na">parent</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">p</span> <span class="o">==</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">left</span><span class="o">)</span>
                <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">left</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
            <span class="k">else</span> <span class="nf">if</span> <span class="o">(</span><span class="n">p</span> <span class="o">==</span> <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">right</span><span class="o">)</span>
                <span class="n">p</span><span class="o">.</span><span class="na">parent</span><span class="o">.</span><span class="na">right</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
            <span class="n">p</span><span class="o">.</span><span class="na">parent</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</code></pre></div>
<p>这个过程同样是与红黑树的性质相关的。在树中删除一个结点，那他的孩子怎么办啊，红黑树不平衡了怎么办啊，树空了怎么办啊，都需要考虑到。</p>

<ul>
<li>clear</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">public</span> <span class="kt">void</span> <span class="nf">clear</span><span class="o">()</span> <span class="o">{</span>
    <span class="n">modCount</span><span class="o">++;</span>
    <span class="n">size</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>居然就是把值都清空了。。</p>

<ul>
<li>clone</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Returns a shallow copy of this {@code TreeMap} instance. (The keys and</span>
<span class="cm"> * values themselves are not cloned.)</span>
<span class="cm"> *</span>
<span class="cm"> * @return a shallow copy of this map</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="n">Object</span> <span class="nf">clone</span><span class="o">()</span> <span class="o">{</span>
    <span class="n">TreeMap</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">clone</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="k">try</span> <span class="o">{</span>
        <span class="n">clone</span> <span class="o">=</span> <span class="o">(</span><span class="n">TreeMap</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;)</span> <span class="kd">super</span><span class="o">.</span><span class="na">clone</span><span class="o">();</span>
    <span class="o">}</span> <span class="k">catch</span> <span class="o">(</span><span class="n">CloneNotSupportedException</span> <span class="n">e</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">throw</span> <span class="k">new</span> <span class="nf">InternalError</span><span class="o">();</span>
    <span class="o">}</span>

    <span class="c1">// Put clone into &quot;virgin&quot; state (except for comparator)</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">root</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">size</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">modCount</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">entrySet</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">navigableKeySet</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">clone</span><span class="o">.</span><span class="na">descendingMap</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>

    <span class="c1">// Initialize clone with our mappings</span>
    <span class="k">try</span> <span class="o">{</span>
        <span class="n">clone</span><span class="o">.</span><span class="na">buildFromSorted</span><span class="o">(</span><span class="n">size</span><span class="o">,</span> <span class="n">entrySet</span><span class="o">().</span><span class="na">iterator</span><span class="o">(),</span> <span class="kc">null</span><span class="o">,</span> <span class="kc">null</span><span class="o">);</span>
    <span class="o">}</span> <span class="k">catch</span> <span class="o">(</span><span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">IOException</span> <span class="n">cannotHappen</span><span class="o">)</span> <span class="o">{</span>
    <span class="o">}</span> <span class="k">catch</span> <span class="o">(</span><span class="n">ClassNotFoundException</span> <span class="n">cannotHappen</span><span class="o">)</span> <span class="o">{</span>
    <span class="o">}</span>

    <span class="k">return</span> <span class="n">clone</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p><code>clone</code> 复制了一份新的元素，使用了 <code>super.clone()</code> 得的一个新对象，而不是使用 <code>new</code>，这是为啥？然后把各个域值清空，然后使用 <code>buildFromSorted</code> 插入数据。之所以使用这个函数，是因为红黑树插入操作时间复杂度为 <code>O(lgn)</code>，n个元素插入就是 <code>O(n*lgn)</code>，太不划算，更何况我们现在插入的是一个红黑树，所以用一个线性时间复杂度的算法来实现复制数据的操作。</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Linear time tree building algorithm from sorted data.  Can accept keys</span>
<span class="cm"> * and/or values from iterator or stream. This leads to too many</span>
<span class="cm"> * parameters, but seems better than alternatives.  The four formats</span>
<span class="cm"> * that this method accepts are:</span>
<span class="cm"> *</span>
<span class="cm"> *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).</span>
<span class="cm"> *    2) An iterator of keys.         (it != null, defaultVal != null).</span>
<span class="cm"> *    3) A stream of alternating serialized keys and values.</span>
<span class="cm"> *                                   (it == null, defaultVal == null).</span>
<span class="cm"> *    4) A stream of serialized keys. (it == null, defaultVal != null).</span>
<span class="cm"> *</span>
<span class="cm"> * It is assumed that the comparator of the TreeMap is already set prior</span>
<span class="cm"> * to calling this method.</span>
<span class="cm"> *</span>
<span class="cm"> * @param size the number of keys (or key-value pairs) to be read from</span>
<span class="cm"> *        the iterator or stream</span>
<span class="cm"> * @param it If non-null, new entries are created from entries</span>
<span class="cm"> *        or keys read from this iterator.</span>
<span class="cm"> * @param str If non-null, new entries are created from keys and</span>
<span class="cm"> *        possibly values read from this stream in serialized form.</span>
<span class="cm"> *        Exactly one of it and str should be non-null.</span>
<span class="cm"> * @param defaultVal if non-null, this default value is used for</span>
<span class="cm"> *        each value in the map.  If null, each value is read from</span>
<span class="cm"> *        iterator or stream, as described above.</span>
<span class="cm"> * @throws IOException propagated from stream reads. This cannot</span>
<span class="cm"> *         occur if str is null.</span>
<span class="cm"> * @throws ClassNotFoundException propagated from readObject.</span>
<span class="cm"> *         This cannot occur if str is null.</span>
<span class="cm"> */</span>
<span class="kd">private</span> <span class="kt">void</span> <span class="nf">buildFromSorted</span><span class="o">(</span><span class="kt">int</span> <span class="n">size</span><span class="o">,</span> <span class="n">Iterator</span> <span class="n">it</span><span class="o">,</span>
                             <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">ObjectInputStream</span> <span class="n">str</span><span class="o">,</span>
                             <span class="n">V</span> <span class="n">defaultVal</span><span class="o">)</span>
    <span class="kd">throws</span>  <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">IOException</span><span class="o">,</span> <span class="n">ClassNotFoundException</span> <span class="o">{</span>
    <span class="k">this</span><span class="o">.</span><span class="na">size</span> <span class="o">=</span> <span class="n">size</span><span class="o">;</span>
    <span class="n">root</span> <span class="o">=</span> <span class="n">buildFromSorted</span><span class="o">(</span><span class="mi">0</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="n">size</span><span class="o">-</span><span class="mi">1</span><span class="o">,</span> <span class="n">computeRedLevel</span><span class="o">(</span><span class="n">size</span><span class="o">),</span>
                           <span class="n">it</span><span class="o">,</span> <span class="n">str</span><span class="o">,</span> <span class="n">defaultVal</span><span class="o">);</span>
<span class="o">}</span>
</code></pre></div>
<p>好吧，我们继续。</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">private</span> <span class="kd">final</span> <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">buildFromSorted</span><span class="o">(</span><span class="kt">int</span> <span class="n">level</span><span class="o">,</span> <span class="kt">int</span> <span class="n">lo</span><span class="o">,</span> <span class="kt">int</span> <span class="n">hi</span><span class="o">,</span>
                                         <span class="kt">int</span> <span class="n">redLevel</span><span class="o">,</span>
                                         <span class="n">Iterator</span> <span class="n">it</span><span class="o">,</span>
                                         <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">ObjectInputStream</span> <span class="n">str</span><span class="o">,</span>
                                         <span class="n">V</span> <span class="n">defaultVal</span><span class="o">)</span>
    <span class="kd">throws</span>  <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">IOException</span><span class="o">,</span> <span class="n">ClassNotFoundException</span> <span class="o">{</span>
    <span class="cm">/*</span>
<span class="cm">     * Strategy: The root is the middlemost element. To get to it, we</span>
<span class="cm">     * have to first recursively construct the entire left subtree,</span>
<span class="cm">     * so as to grab all of its elements. We can then proceed with right</span>
<span class="cm">     * subtree.</span>
<span class="cm">     *</span>
<span class="cm">     * The lo and hi arguments are the minimum and maximum</span>
<span class="cm">     * indices to pull out of the iterator or stream for current subtree.</span>
<span class="cm">     * They are not actually indexed, we just proceed sequentially,</span>
<span class="cm">     * ensuring that items are extracted in corresponding order.</span>
<span class="cm">     */</span>

    <span class="k">if</span> <span class="o">(</span><span class="n">hi</span> <span class="o">&lt;</span> <span class="n">lo</span><span class="o">)</span> <span class="k">return</span> <span class="kc">null</span><span class="o">;</span>

    <span class="kt">int</span> <span class="n">mid</span> <span class="o">=</span> <span class="o">(</span><span class="n">lo</span> <span class="o">+</span> <span class="n">hi</span><span class="o">)</span> <span class="o">&gt;&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>

    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">left</span>  <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">lo</span> <span class="o">&lt;</span> <span class="n">mid</span><span class="o">)</span>
        <span class="n">left</span> <span class="o">=</span> <span class="n">buildFromSorted</span><span class="o">(</span><span class="n">level</span><span class="o">+</span><span class="mi">1</span><span class="o">,</span> <span class="n">lo</span><span class="o">,</span> <span class="n">mid</span> <span class="o">-</span> <span class="mi">1</span><span class="o">,</span> <span class="n">redLevel</span><span class="o">,</span>
                               <span class="n">it</span><span class="o">,</span> <span class="n">str</span><span class="o">,</span> <span class="n">defaultVal</span><span class="o">);</span>

    <span class="c1">// extract key and/or value from iterator or stream</span>
    <span class="n">K</span> <span class="n">key</span><span class="o">;</span>
    <span class="n">V</span> <span class="n">value</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">it</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">defaultVal</span><span class="o">==</span><span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">entry</span> <span class="o">=</span> <span class="o">(</span><span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;)</span><span class="n">it</span><span class="o">.</span><span class="na">next</span><span class="o">();</span>
            <span class="n">key</span> <span class="o">=</span> <span class="n">entry</span><span class="o">.</span><span class="na">getKey</span><span class="o">();</span>
            <span class="n">value</span> <span class="o">=</span> <span class="n">entry</span><span class="o">.</span><span class="na">getValue</span><span class="o">();</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">key</span> <span class="o">=</span> <span class="o">(</span><span class="n">K</span><span class="o">)</span><span class="n">it</span><span class="o">.</span><span class="na">next</span><span class="o">();</span>
            <span class="n">value</span> <span class="o">=</span> <span class="n">defaultVal</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span> <span class="c1">// use stream</span>
        <span class="n">key</span> <span class="o">=</span> <span class="o">(</span><span class="n">K</span><span class="o">)</span> <span class="n">str</span><span class="o">.</span><span class="na">readObject</span><span class="o">();</span>
        <span class="n">value</span> <span class="o">=</span> <span class="o">(</span><span class="n">defaultVal</span> <span class="o">!=</span> <span class="kc">null</span> <span class="o">?</span> <span class="n">defaultVal</span> <span class="o">:</span> <span class="o">(</span><span class="n">V</span><span class="o">)</span> <span class="n">str</span><span class="o">.</span><span class="na">readObject</span><span class="o">());</span>
    <span class="o">}</span>

    <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">middle</span> <span class="o">=</span>  <span class="k">new</span> <span class="n">Entry</span><span class="o">&lt;&gt;(</span><span class="n">key</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="kc">null</span><span class="o">);</span>

    <span class="c1">// color nodes in non-full bottommost level red</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">level</span> <span class="o">==</span> <span class="n">redLevel</span><span class="o">)</span>
        <span class="n">middle</span><span class="o">.</span><span class="na">color</span> <span class="o">=</span> <span class="n">RED</span><span class="o">;</span>

    <span class="k">if</span> <span class="o">(</span><span class="n">left</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">middle</span><span class="o">.</span><span class="na">left</span> <span class="o">=</span> <span class="n">left</span><span class="o">;</span>
        <span class="n">left</span><span class="o">.</span><span class="na">parent</span> <span class="o">=</span> <span class="n">middle</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="k">if</span> <span class="o">(</span><span class="n">mid</span> <span class="o">&lt;</span> <span class="n">hi</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Entry</span><span class="o">&lt;</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">&gt;</span> <span class="n">right</span> <span class="o">=</span> <span class="n">buildFromSorted</span><span class="o">(</span><span class="n">level</span><span class="o">+</span><span class="mi">1</span><span class="o">,</span> <span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="o">,</span> <span class="n">hi</span><span class="o">,</span> <span class="n">redLevel</span><span class="o">,</span>
                                           <span class="n">it</span><span class="o">,</span> <span class="n">str</span><span class="o">,</span> <span class="n">defaultVal</span><span class="o">);</span>
        <span class="n">middle</span><span class="o">.</span><span class="na">right</span> <span class="o">=</span> <span class="n">right</span><span class="o">;</span>
        <span class="n">right</span><span class="o">.</span><span class="na">parent</span> <span class="o">=</span> <span class="n">middle</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="k">return</span> <span class="n">middle</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p>可以看出这是一个递归的算法，找出中间结点，构造左右子树，并将他们连接在一起。时间复杂度分析可以根据递归式：</p>

<blockquote>
<p>T(n) = 2 * T(n/2) + C</p>
</blockquote>

<p>如果看不出来的话，可以使用《算法导论》第4章中的主定理，可以得到时间复杂度为 <code>O(n)</code> 。</p>


      </article>

      <div class="comments">
        
          <div id="disqus_thread"></div>
 <script type="text/javascript">
     /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
     var disqus_shortname = 'minixalpha'; // required: replace example with your forum shortname

     /* * * DON'T EDIT BELOW THIS LINE * * */
     (function() {
         var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
         dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
         (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
     })();
 </script>
 <noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
    

        
      </div>


      <footer>
        Copyright (c) minixalpha 2014
      </footer>

    </div>
  </body>
</html>
